package com.example.algorithm.dynamicprogramming;

import java.util.*;

/**
 * 给定一个整数数组 A，你可以从某一起始索引出发，跳跃一定次数。在你跳跃的过程中，第 1、3、5... 次跳跃称为奇数跳跃，而第 2、4、6... 次跳跃称为偶数跳跃。
 * <p>
 * 你可以按以下方式从索引 i 向后跳转到索引 j（其中 i < j）：
 * 在进行奇数跳跃时（如，第 1，3，5... 次跳跃），你将会跳到索引 j，使得 A[i] <= A[j]，A[j] 是可能的最小值。
 * 如果存在多个这样的索引j，你只能跳到满足要求的最小索引 j 上。
 * 在进行偶数跳跃时（如，第 2，4，6... 次跳跃），你将会跳到索引 j，使得 A[i] >= A[j]，A[j] 是可能的最大值。
 * 如果存在多个这样的索引j，你只能跳到满足要求的最小索引 j 上。
 * （对于某些索引 i，可能无法进行合乎要求的跳跃。）
 * <p>
 * 如果从某一索引开始跳跃一定次数（可能是 0 次或多次），就可以到达数组的末尾（索引 A.length - 1），那么该索引就会被认为是好的起始索引。
 * 返回好的起始索引的数量。
 * <p>
 * 示例 1：
 * 输入：[10,13,12,14,15]
 * 输出：2
 * 解释：
 * 从起始索引 i = 0 出发，我们可以跳到 i = 2，（因为 A[2] 是 A[1]，A[2]，A[3]，A[4] 中大于或等于 A[0] 的最小值），然后我们就无法继续跳下去了。
 * 从起始索引 i = 1 和 i = 2 出发，我们可以跳到 i = 3，然后我们就无法继续跳下去了。
 * 从起始索引 i = 3 出发，我们可以跳到 i = 4，到达数组末尾。
 * 从起始索引 i = 4 出发，我们已经到达数组末尾。
 * 总之，我们可以从 2 个不同的起始索引（i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。
 * <p>
 * 示例 2：
 * 输入：[2,3,1,1,4]
 * 输出：3
 * 解释：
 * 从起始索引 i=0 出发，我们依次可以跳到 i = 1，i = 2，i = 3：
 * 在我们的第一次跳跃（奇数）中，我们先跳到 i = 1，因为 A[1] 是（A[1]，A[2]，A[3]，A[4]）中大于或等于 A[0] 的最小值。
 * 在我们的第二次跳跃（偶数）中，我们从 i = 1 跳到 i = 2，因为 A[2] 是（A[2]，A[3]，A[4]）中小于或等于 A[1] 的最大值。
 * A[3] 也是最大的值，但 2 是一个较小的索引，所以我们只能跳到 i = 2，而不能跳到 i = 3。
 * <p>
 * 在我们的第三次跳跃（奇数）中，我们从 i = 2 跳到 i = 3，因为 A[3] 是（A[3]，A[4]）中大于或等于 A[2] 的最小值。
 * 我们不能从 i = 3 跳到 i = 4，所以起始索引 i = 0 不是好的起始索引。
 * 类似地，我们可以推断：
 * 从起始索引 i = 1 出发， 我们跳到 i = 4，这样我们就到达数组末尾。
 * 从起始索引 i = 2 出发， 我们跳到 i = 3，然后我们就不能再跳了。
 * 从起始索引 i = 3 出发， 我们跳到 i = 4，这样我们就到达数组末尾。
 * 从起始索引 i = 4 出发，我们已经到达数组末尾。
 * 总之，我们可以从 3 个不同的起始索引（i = 1, i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。
 * <p>
 * 示例 3：
 * 输入：[5,1,3,4,2]
 * 输出：3
 * 解释：
 * 我们可以从起始索引 1，2，4 出发到达数组末尾。
 */
public class Leetcode975_OddEvenJumps {
    public static void main(String[] args) {
        int[] nums = {10, 13, 12, 14, 15};
//        TreeMap<Integer, Integer> map = new TreeMap();
//        for (int i = 0; i < nums.length; i++) {
//            map.put(nums[i], i);
//        }
//        System.out.println(map.floorKey(11));
//        System.out.println(map.ceilingKey(11));
//        map.forEach((k, v) -> System.out.println(k + "-->" + v));
        System.out.println(new Solution().oddEvenJumps(nums));
    }

    static class Solution {


        /**
         * 解法四:单调栈优化动态规划
         * 每次求下一跳都得遍历元素之后得所有元素非常耗时
         * 使用单调栈预先算出每个元素的下一跳(奇数跳和偶数跳)位置,然后每次直接取即可
         * <p>
         * 单调栈:栈中数据出栈 的序列为单调递增(减)序列
         * 对数组进行升序排序（快排，需要保留 索引序列
         * 基于升序数组及索引序列使用单调递增栈，求下一个奇数跳索引位置
         * 基于降序数组及索引序列使用单调递增栈，求下一个偶数跳索引位置
         *
         * @param arr
         * @return
         */
        private int oddEvenJumps4(int[] arr) {
            int length = arr.length, count = 1; //好起始索引数
            // 备忘录，从第i个位置跳是否可行
            boolean[] odd = new boolean[length], even = new boolean[length];
            // 提前计算每个位置的下一个位置,值为0表示不能跳跃
            int[] oddNexts = new int[length], evenNexts = new int[length];
            int[] index = new int[length];//维护排序后数组在排序前的索引值
            int[] newA = Arrays.copyOf(arr, length);

            for (int i = 0; i < length; i++) index[i] = i;
            nextPos(newA, index, oddNexts);//计算奇数跳各个位置的下一跳位置
            for (int i = 0; i < length; i++) { //偶数跳时将value*-1，转成和奇数跳一致的方式
                newA[i] = arr[i] * -1;
                index[i] = i;
            }
            nextPos(newA, index, evenNexts);//计算偶数跳
            odd[length - 1] = even[length - 1] = true;
            for (int i = length - 2; i >= 0; i--) { //该位置奇数跳是否可行、偶数跳是否可行
                int nextPos = oddNexts[i];
                if (nextPos == arr.length - 1) odd[i] = true;//到达终点
                else if (nextPos != 0) odd[i] = even[nextPos];//取决于后面是否可行
                if (odd[i]) count++;
                nextPos = evenNexts[i];
                if (nextPos == arr.length - 1) even[i] = true;//到达终点
                else if (nextPos != 0) even[i] = odd[nextPos];//取决于后面是否可行
            }
            return count;
        }

        //改造为稳定的快速排序
        private void quickSort(int arr[], int[] index, int low, int high) {
            int i = low; //i是向后搜索指针
            int j = high;//j是向前搜索指针
            int temp = arr[i];
            int tempIndex = index[i];
            while (i < j) {

                while (i < j && arr[j] >= temp) {
                    if (arr[j] == temp && index[j] < tempIndex) break;
                    j--; //arr[j]不小于基准，不用交换，继续向前搜索
                }

                if (i < j) {
                    index[i] = index[j];
                    arr[i++] = arr[j]; //比arr[0]小的记录移到前面
                }

                while (i < j && arr[i] <= temp) {
                    if (arr[i] == temp && index[i] > tempIndex) break;
                    i++;//arr[i] 不大于基准，不用交换，继续向后搜索
                }

                if (i < j) {
                    index[j] = index[i];
                    arr[j--] = arr[i];//比arr[0]大的记录移到后面
                }
            }
            arr[i] = temp;//确定基准记录位置
            index[i] = tempIndex;
            if (low < i - 1) quickSort(arr, index, low, i - 1); //递归处理左子区
            if (high > i + 1) quickSort(arr, index, i + 1, high); //递归处理右子区
        }

        private void nextPos(int[] newA, int[] index, int[] pos) {
            quickSort(newA, index, 0, newA.length - 1);//value 和key排序
            Deque<Integer> stack = new LinkedList<>();
            for (int i = 0; i < newA.length; i++) {//遍历有序数组，使用单调栈找到下一个位置
                while (!stack.isEmpty() && index[i] > stack.peek())//栈不为空且 栈顶小于index
                    pos[stack.pop()] = index[i];//栈顶出栈并将index填入其下一跳跃位置
                stack.push(index[i]);//index入栈
            }
        }

        /**
         * 解法三:TreeMap优化动态规划
         * 每次求下一跳都得遍历元素之后得所有元素非常耗时
         * TreeMap会对map按照key进行排序
         * 使用treeMap寻找下一跳位置就不需要遍历
         * <p>
         * 其他地方同动态规划一样
         *
         * @param arr
         * @return
         */
        private int oddEvenJumps3(int[] arr) {
            int len = arr.length;
            int count = 1;
            // 优化一:使用两个数组分别存放从i开始进行奇数(偶数)次跳跃能否到达终点(一维数组比二维效率高)
            boolean[] odd = new boolean[len];
            boolean[] even = new boolean[len];
            odd[len - 1] = even[len - 1] = true;// 最后的元素无论是奇数跳还是偶数跳都能成功
            // 优化二
            TreeMap<Integer, Integer> map = new TreeMap<>(); // key：对应数组的值 value：对应数组的索引 位置
            map.put(arr[len - 1], len - 1);

            for (int i = len - 2; i >= 0; i--) {// 从倒数第二个元素开始向前遍历求该元素是否是一个好的索引位置
                int tmp = arr[i];
                // 判断奇数跳能否成功
                Map.Entry<Integer, Integer> higherEntry = map.ceilingEntry(tmp);
                if (higherEntry != null) {
                    Integer nextPos = higherEntry.getValue();
                    odd[i] = even[nextPos]; //当前的元素能否奇数跳到最后要取决于下一跳元素是否能偶数跳到最后
                }

                // 判断偶数跳能否成功
                Map.Entry<Integer, Integer> lowerEntry = map.floorEntry(arr[i]);
                if (lowerEntry != null) {
                    Integer nextPos = lowerEntry.getValue();
                    even[i] = odd[nextPos]; //当前的元素能否偶数跳到最后要取决于下一跳元素是否能奇数跳到最后
                }

                count = odd[i] ? ++count : count; // 记录能够通过奇数跳到达终点的元素个数

                map.put(arr[i], i);
            }

            return count;
        }

        /**
         * 解法二:动态规划
         * 重叠子问题
         * j前面的多个位置都有可能经过1次或多次跳跃到达j处,暴力法有很多重复计算
         * 无后效性
         * j后状态只与到达j位置的步数奇偶性有关(从j开始奇数次跳跃能否到终点或者从j开始偶数次跳跃能否到终点)，与从哪个位置跳来无关
         * 最优子结构
         * 可以通过前面的状态推导出后面的状态
         * 综上:满足动态规划的条件
         * <p>
         * 原问题与子问题:
         * 1.子问题:
         * 求解从j开始奇数次跳跃能否到终点,或者从j开始偶数次跳跃能否到终点
         * <p>
         * 2.设计状态:
         * <p>
         * 3.状态转移方程:
         * f(i,o)=f(j,e) 第i个位置奇数跳可行,转化为判断第j个位置偶数跳是否可行
         * f(i,e)=f(k,o) 第i个位置偶数跳可行,转化为判断第k个位置奇数跳是否可行
         * 其中o为奇数跳，e为偶数跳
         * j为从i进行奇数次跳跃后的位置，k为从i进行偶数次跳跃后的位置
         * <p>
         * 从后向前推导每个位置的可行性(因为最后元素一定是可行的,可以通过判断倒数第二个元素是否可以以它为起点通过奇偶跳跳到最后一个元素,前面的所有元素都可以依次类推)
         * 目标值:从i开始进行奇数跳可行的元素个数
         * 4.边界值:
         *
         * @param arr
         * @return
         */
        private int oddEvenJumps2(int[] arr) {
            int len = arr.length;
            int count = 0;
            // dp[i][0]从i开始进行奇数跳跃是否可行;dp[i][1]从i开始进行偶数跳跃是否可行
            boolean[][] dp = new boolean[len][2];
            // 数组的末尾进行奇偶跳肯定可行
            dp[len - 1][0] = true;
            dp[len - 1][1] = true;
            for (int i = len - 1; i >= 0; i--) {
                int nextPos;
                // 判断以当前位置开始进行奇数跳能否到到达终点(是否可行)
                nextPos = nextPos(arr, i, true);
                if (nextPos == len - 1) { // 下一跳为终点说明可行
                    dp[i][0] = true;
                } else if (nextPos != -1) { // 下一跳为i之后的其他位置(不为-1或者终点)要取决于下一跳的偶数跳是否可行
                    dp[i][0] = dp[nextPos][1];
                }

                // 判断以当前位置开始进行偶数跳能否到到达终点(是否可行)
                nextPos = nextPos(arr, i, false);
                if (nextPos == len - 1) {
                    dp[i][1] = true;
                } else if (nextPos != -1) {// 下一跳为i之后的其他位置(不为-1或者终点)要取决于下一跳的奇数跳是否可行
                    dp[i][1] = dp[nextPos][0];
                }

                count = dp[i][0] ? ++count : count; // 记录能够通过奇数跳到达终点的元素个数
            }
            return count;
        }

        /**
         * 解法一:暴力法
         * 遍历每个元素按照奇偶跳的规则进行尝试
         *
         * @param arr
         * @return
         */
        private int oddEvenJumps1(int[] arr) {
            int count = 0;
            for (int i = 0; i < arr.length; i++) {
                int step = 1;
                int nextPos = i;
                while (nextPos != arr.length - 1 && nextPos != -1) {// -1说明不存在下一跳位置
                    nextPos = nextPos(arr, nextPos, (step % 2) == 1);
                    step++;
                }

                count = (nextPos == arr.length - 1) ? ++count : count; //可以到达终点，好起始索引个数+1
            }

            return count;
        }

        private int nextPos(int[] arr, int start, boolean isOdd) {
            int tmp = arr[start];
            int nextPos = -1;
            int curVal = isOdd ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            // 10, 13, 12, 14, 15
            if (isOdd) { // 奇数次跳跃寻找该元素后面比大的z最小值
                for (int j = start + 1; j < arr.length; j++) {
                    if (arr[j] >= tmp && arr[j] < curVal) {
                        curVal = arr[j];
                        nextPos = j;
                    }
                }
            } else {// 偶数次跳跃寻找该元素后面比小的最大值
                for (int j = start + 1; j < arr.length; j++) {
                    if (arr[j] <= tmp && arr[j] > curVal) {
                        curVal = arr[j];
                        nextPos = j;
                    }
                }
            }
            return nextPos;
        }

        public int oddEvenJumps(int[] arr) {
            return oddEvenJumps4(arr);
        }
    }
}
